package com.huawei.tree;

import com.huawei.common.TreeNode;

/**
 * @Author admin
 * @Description 验证二叉搜索树
 * @Date 2023/11/12/11:09
 * @Version 1.0
 */
public class VerifyBinarySearchTree {

	public static void main(String[] args) {
		TreeNode root1 = new TreeNode(2);
		root1.left = new TreeNode(1);
		root1.right = new TreeNode(3);
		System.out.println(VerifyBinarySearchTree.isValidBST(root1));
	}

	public static boolean isValidBST(TreeNode root) {
		return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
	}

	/**
	 * 对于二叉搜索树的每个节点，它的值必须在它的上下界之间。对于一个节点，它的上下界取决于它的父节点的值。
	 * 对于根节点，它的上下界是整个可能的值域（在本例中是Long的最小值和最大值）。
	 * 对于左子节点，它的上界是父节点的值，下界是整个可能的值域。
	 * 对于右子节点，它的下界是父节点的值，上界是整个可能的值域。因此，对于每个节点，我们都可以使用上述方法来验证它是否是二叉搜索树的一部分。
	 * @param node
	 * @param minVal
	 * @return
	 */
	private static boolean isValidBST(TreeNode node, long minVal, long maxVal) {
		if (node == null) return true;
		if (node.val >= maxVal || node.val <= minVal) return false;
		return isValidBST(node.left, minVal, node.val) && isValidBST(node.right, node.val, maxVal);
	}
}
